<template>
    <div class="demo-collapse">
        <el-collapse v-model="activeNames" @change="handleChange">
            <el-collapse-item title="解题思路" name="thinking">
                <div>
                    <div>
                        1.初始时为只有n 个顶点而无边的非连通图 T 每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序；
                    </div>
                    <div>
                        2.不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入 T , 
                        否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。
                    </div>
                    <div>
                        <img src="../../../../../../assets/最小生成树/最小生成树3.png" alt="">
                    </div>
                </div>
            </el-collapse-item>
            <el-collapse-item title="代码实现" name="code">
                <!-- <el-image style="width:100%" :src="url" :fit="fit" loading="lazy"></el-image> -->
                <div v-highlight>
                    <div>C/C++:</div>
                    <pre class="language-javascript">
                      <code>
                        #include&lt;iostream>
                        using namespace std;
                        char node[1000];

                        /**  （1）图的存储结构  **/
                        //节点集 
                        typedef struct Node{
	                        char a,b;  //起点和终点 
	                        int w;     //权值 
                        }Node; 
                        //边集
                        typedef struct{
	                        int len,n;  //长度和顶点的个数 
	                        Node *list; //指针 
                        }Graph;


                        /**  （2）线性表的初始化  **/
                        int InitList(Graph &G){
	                        G.len=0;
	                        G.list=new Node[1000];
	                        return 0;
                        } 

                        /**  （3）线性表赋初值 **/
                        int GetList(Graph &G){
	                        cout&lt;&lt;"输入节点的个数和边的条数"&lt;&lt;endl;
	                        cin>>G.len>>G.n;
	                        cout&lt;&lt;"输入节点的名称"&lt;&lt;endl;
	                        for(int i=1;i&lt;=G.len;i++)
		                        cin>>node[i];
	                        cout&lt;&lt;"输入边起点，终点，权值"&lt;&lt;endl;
	                        G.list[0].w=0;
	                        for(int i=1;i&lt;=G.n;i++)
		                        cin>>G.list[i].a>>G.list[i].b>>G.list[i].w;
	                        return 0;
                        } 

                        /**  线性表的按权值插入排序 **/
                        int InsertList(Graph G){
	                        int j=0;
	                        for(int i=2;i&lt;=G.n;i++){
		                        if(G.list[i].w&lt;G.list[i-1].w){
			                        G.list[0]=G.list[i];
			                        G.list[i]=G.list[i-1];
			                        for(j=i-2;G.list[0].w&lt;G.list[j].w;j--)
			                            G.list[j+1]=G.list[j];
			                        G.list[j+1]=G.list[0];
		                        }		   
	                        }
	                        return 0;
                        }

                        /**  (4)查找源头  **/
                        int GetRoot(Graph G,int V[],char x){
	                        int y;
	                        //将要查询的数转化为并查集数
	                        for(int i=1;i&lt;=G.len;i++)
		                        if(node[i]==x)y=i;
	                        //查源 
	                        while(V[y]!=y)
	                            y=V[y];
	                        cout&lt;&lt;x&lt;&lt;"的源头为："&lt;&lt;y&lt;&lt;endl; 
	                        return y;
	
                        }

                        /** 输(5)出选择路径  **/
                        int Pop(Graph G,int data[],int t){
	                        int m;
	                        //输出 
	                        cout&lt;&lt;"选择的边和权值为："&lt;&lt;endl; 
	                        for(int i=0;i&lt;t;i++){
		                        m=data[i];
		                        cout&lt;&lt;G.list[m].a&lt;&lt;"-->"&lt;&lt;G.list[m].b&lt;&lt;" :"&lt;&lt;G.list[m].w&lt;&lt;endl; 
	                        }
	                        return 0;
                        }

                        /**  Kruskal算法  **/
                        int Kruskal(Graph G){
                            //记录最短路径 
	                        int sum=0,t=0;  
	                        int data[1000];
	                        //并查集
	                        int V[1000]; 
	                        //并查集初始化 
	                        for(int i=1;i&lt;=G.len;i++)
		                        V[i]=i;
	                        //算法核心 
	                        for(int i=1;i&lt;=G.n;i++){
		                        int v1,v2;
		                        //查找源头
		                        v1=GetRoot(G,V,G.list[i].a); //起点源头 
		                        v2=GetRoot(G,V,G.list[i].b); //终点源头 
		                        if(v1!=v2){
		                            sum+=G.list[i].w;
			                        V[v1]=v2; //A--C: V[A的源头B] = C的源头C
			                        for(int k=1;k&lt;=3;k++)
			                        cout&lt;&lt;"V["&lt;&lt;k&lt;&lt;"]="&lt;&lt;V[k]&lt;&lt;endl;
			                        data[t]=i; //记录回帖的边 
			                        t++;
		                        }
	                        } 
	
	                        Pop(G,data,t);
	                        return sum;
                        }


                        int main(){
	                        Graph G;
	                        InitList(G);
	                        GetList(G);
	                        InsertList(G);
	                        cout&lt;&lt;"最短路径为： "&lt;&lt;Kruskal(G);
	                        return 0;
                        } 

                      </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Java:</div>
                    <pre class="language-javascript">
                        <code>                  
                            import java.util.Arrays;
                            import java.util.Comparator;
                            import java.util.Scanner;

                            public class _最小生成树kruskal {
	
	                            static class Edge{
		                            int left;
		                            int right;
		                            int weight;
		                            Edge(){}
	                            }
	                            static int maxn=100;//边数的最大值
	                            static Edge []edge;//一开始只需要声明，不需要实例化数量，在main函数中实例化，否则就会出现空指针问题，在Arrays.sort的时候
	                            static int []father=new int [maxn];//并查集的父亲数组
	                            static Comparator&lt;Edge>cmp=new Comparator &lt;Edge>() {
		                            public int compare(Edge acd,Edge bfc) {
			                            return (acd.weight-bfc.weight);//升序
		                            }
	                            };
	                            static int findfather(int x) {
		                            int a=x;
		                            while(x!=father[x])//一开始的father数组初始化为自己
		                            {
			                            x=father[x];
		                            }
		                            //路径压缩
		                            while(a!=father[a]) {
			                            int z=a;
			                            a=father[a];//走下一步
			                            father[z]=x;//改上一步的父亲
		                            }
		                            return x;
	                            }
	                            static int kruskal(int n,int m)//返回最小生成树的边权重之和，n为顶点数，m为维数
	                            {
		                            int ans=0;int edgenumber=0;
		                            for(int i=0;i&lt;n;i++) {
			                            father[i]=i;//初始化并查集数组
		                            }
		                            Arrays.sort(edge,cmp);
		                            for(int i=0;i&lt;m;i++) {
			                            int a=findfather(edge[i].left);
			                            int b=findfather(edge[i].right);
			                            if(a!=b) {
				                            father[a]=b;
				                            ans=ans+edge[i].weight;
				                            edgenumber++;
				                            if(edgenumber==n-1) {
					                            break;//边数等于顶点数-1，说明找到了一个最小生成树
				                            }
			                            }
		                            }
		                            if(edgenumber==n-1) return ans;
		                            else return -1;//说明没有连通的最小生成树
	                            }
	                            public static void main(String []args) {
		                            Scanner cin=new Scanner (System.in);
		                            int n,m;
		                            n=cin.nextInt();m=cin.nextInt();
		                            edge=new Edge[m];
		                            for(int k=0;k&lt;m;k++) {
			                            edge[k]=new Edge();
		                            }
		                            //其实也可以在这里初始化并查集的,但是选择在Kruskal里面处理了
		                            for(int i=0;i&lt;m;i++) {
			                            edge[i].left=cin.nextInt();
			                            edge[i].right=cin.nextInt();
			                            edge[i].weight=cin.nextInt();
		                            }
		                            int ans=kruskal(n,m);
		                            System.out.println(ans);
	                            }
                            }


                        </code>
                    </pre>
                </div>
                <div v-highlight>
                    <div>Python:</div>
                    <pre class="language-javascript">
                      <code>
                        import time                         
                        start = time.perf_counter() #开始计时
                        class DisjointSet(dict):
                            '''不相交集'''

                            def __init__(self, dict):
                                pass

                            def add(self, item):
                                self[item] = item

                            def find(self, item):
                                if self[item] != item:
                                    self[item] = self.find(self[item])
                                return self[item]

                            def unionset(self, item1, item2):
                                self[item2] = self[item1]

                        def Kruskal(nodes, edges):
                            '''基于不相交集实现Kruskal算法'''
                            forest = DisjointSet(nodes)
                            MST = []
                            for item in nodes:
                                forest.add(item)
                            edges = sorted(edges, key=lambda element: element[2])
                            num_sides = len(nodes)-1  # 最小生成树的边数等于顶点数减一
                            for e in edges:
                                node1, node2, _ = e
                                parent1 = forest.find(node1)
                                parent2 = forest.find(node2)
                                if parent1 != parent2:
                                    MST.append(e)
                                    num_sides -= 1
                                    if num_sides == 0:
                                        return MST
                                    else:
                                        forest.unionset(parent1, parent2)
                            pass

                        def main():
                            nodes = set(list('ABCDE'))
                            edges = [("A", "B", 1), ("A", "C", 7),
                                    ("A", "D", 3), ("B", "C", 6),
                                    ("B", "E", 4), ("C", "D", 8),
                                    ("C", "E", 5), ("D", "E", 2)]
                            print("\n\nThe undirected graph is :", edges)
                            print("\n\nThe minimum spanning tree by Kruskal is : ")
                            print(Kruskal(nodes, edges))

                        if __name__ == '__main__':
                            main()
                        end = time.perf_counter()
                        print('Running time: %f seconds'%(end-start))
                        import time
                        start = time.perf_counter()
                        class DisjointSet(dict):
                            '''不相交集'''

                            def __init__(self, dict):
                                pass

                            def add(self, item):
                                self[item] = item

                            def find(self, item):
                                if self[item] != item:
                                    self[item] = self.find(self[item])
                                return self[item]

                            def unionset(self, item1, item2):
                                self[item2] = self[item1]

                        def Kruskal(nodes, edges):
                            '''基于不相交集实现Kruskal算法'''
                            forest = DisjointSet(nodes)
                            MST = []
                            for item in nodes:
                                forest.add(item)
                            edges = sorted(edges, key=lambda element: element[2])
                            num_sides = len(nodes)-1  # 最小生成树的边数等于顶点数减一
                            for e in edges:
                                node1, node2, _ = e
                                parent1 = forest.find(node1)
                                parent2 = forest.find(node2)
                                if parent1 != parent2:
                                    MST.append(e)
                                    num_sides -= 1
                                    if num_sides == 0:
                                        return MST
                                    else:
                                        forest.unionset(parent1, parent2)
                            pass

                        def main():
                            nodes = set(list('ABCDEFG'))
                            edges = [("A", "B", 7), ("A", "D", 5),
                                    ("B", "C", 8), ("B", "D", 9), ("B", "E", 7), 
                                    ("C", "E", 5), ("D", "E", 15), ("D", "F", 6),
                                    ("E", "F", 8), ("E", "G", 9), ("F", "G", 11)]
                            print("\n\nThe undirected graph is :", edges)
                            print("\n\nThe minimum spanning tree by Kruskal is : ")
                            print(Kruskal(nodes, edges))

                        if __name__ == '__main__':
                            main()
                        end = time.perf_counter()   #结束计时
                        print('Running time: %f seconds'%(end-start))  #程序运行时间


                      </code>
                    </pre>
                </div>
            </el-collapse-item>
        </el-collapse>
    </div>
</template>

<script lang="ts" setup>
import { ref } from 'vue'
const activeNames = ref(['thinking'])
const handleChange = (val: string[]) => {
    console.log(val)
}
// 代码实现部分
import "vue-code-highlight/themes/prism-solarizedlight.css";
import "vue-code-highlight/themes/window.css";

</script>
